1. Field of the Invention
The present invention relates to an associative memory and search method, and more particularly to an associative memory having a masking function.
2. Background of the Invention
As disclosed in the Japanese Unexamined Patent Publication (KOKAI) No.1-220293, an associative memory having mask information for each individual word or plurality of words has writing, and reading functions by specify the address such as a conventional memory, and additionally has a function of searching the memory for an address that has stored data that is the same as search data that is input to the memory, a masking function in which masking information is used to eliminate part of the stored data from a search operation, and a function of outputting an address at which the contents coincided with the specified search data.
Additionally, as disclosed in the Japanese Unexamined Patent Publication (KOKAI) No.11-073782, there is an associative memory that has a function which, when a plurality of stored data coincide with search data, selects the data that has the shortest mask.
The associative memory with a shortest mask output function disclosed in the Japanese Unexamined Patent Publication (KOKAI) No.11-073782 can be described as follows.
FIG. 8 is a block diagram of an example of the configuration of an associative memory with a shortest mask output function as disclosed in the Japanese Unexamined Patent Application publication H11-073782.
Referring to FIG. 8, this associative memory has an n-bit 2-input/1-output selector 17, m-word/n-bit associative memories 8-1 to 8-m, and an n-bit latch 21.
Each associative memory word 8-j (where 1.ltoreq.k.ltoreq.m) has associative memory cells 12-j-1 to 12-j-n, and a latch 20-j.
Each associative memory cell 12-j-k (where 1.ltoreq.k.ltoreq.n, and 1.ltoreq.j.ltoreq.m) has data cells 9-j-k (where 1.ltoreq.k.ltoreq.n and 1.ltoreq.j.ltoreq.m) which stores data, comparators 11-j-k for performing a comparison between bit information stored in the data cells 9-j-k and the bit information 105-k corresponding to the externally input search data, mask cells 10-j-k which stores bit information corresponding to the mask information, mask comparators 18-j-k for performing a comparison between bit information stored in the mask cells 10-j-k and the bit information 22-k corresponding to the shortest mask information output from the n-bit latch 21, and logic circuit 13-j-k.
FIG. 9 shows an example of the configuration of an associative memory cell, in which the two bit lines 6a and 6b correspond to the bit lines shown in FIG. 8, this being represented in FIG. 8 by 6-i (where 1.ltoreq.i.ltoreq.n).
Writing of data into the associative memory cells and input of search data is performed via these two bit lines 6a and 6b.
In the case of writing data and the case of inputting search data, the data input to the bit line 6b is the data value of bit line 6a inverted.
The data cell 9 has the inverter (G1) 201 and the inverter (G2) 202, the inputs and outputs of which are mutually cross-connected so as to form a flip-flip, a MOS transistor (T1) 203 which serves as a transfer gate, inserted between the output end of the inverter (G2) 202 and the bit line 6a, a gate of which is connected to the data word line 14, this transistor 203 being placed in the conducting and non-conducting states by the high and low levels, respectively, of the data word line 14, and a MOS transistor (T2) 204 which serves as a transfer gate, inserted between the output end of the inverter (G1) 201 and the bit line 6b, a gate of which is connected to the data word line 14, this transistor 204 being placed in the conducting and non-conducting states by the high and low levels, respectively, of the data word line 14, the configuration of this data cell 9 being equivalent to that of a conventional static RAM (SRAM) element.
Similarly , the mask cell 10 has inverter (G3) 209 and the inverter (G4) 210, the inputs and outputs of which are mutually cross-connected so as to form a flip-flip, a MOS transistor (T7) 211 which serves as a transfer gate, inserted between the output end of the inverter (G4) 210 and the bit line 6a, gate of which is connected to the data word line 15, this transistor 211 being placed in the conducting and non-conducting states by the high and low levels, respectively, of the data word line 15, and a MOS transistor (T8) 212 which serves as a transfer gate, inserted between the output end of the inverter (G3) 209 and the bit line 6b, a gate of which is connected to the data word line 15, this transistor being placed in the conducting and non-conducting states by the high and low levels, respectively, of the data word line 15, the configuration of this mask cell 10 as well being equivalent to that of a conventional static SRAM element.
The comparator 11 is formed by a MOS transistor (T3) 205, a MOS transistor (T4) 206, a MOS transistor (T5) 207, and a MOS transistor (T6) 208.
The MOS transistor (T3) 205 and the MOS transistor (T4) 206 are connected in series between bit lines 6a and 6b, the gate of MOS transistor (T3) 205 being connected to the output of the inverter (G1) 201 in the data cell 9, this transistor 205 going into the conducting condition when the output end of the inverter (G1) 201 is at the high level. The gate of the MOS transistor (T4) 206 is connected to the output end of the inverter (G2) 202 in the data cell 9, this transistor 206 going into the conducting condition when the output end of the inverter (G2) 202 is at the high level.
The MOS transistor (T5) 207 and the MOS transistor (T6) 208 are connected in series between a low-potential power supply and the coincidence line 7, the gate of the MOS transistor (T5) 207 being connected to the connection node between the MOS transistor (T3) 205 and the MOS transistor (T4) 206, this transistor 207 going into the conducting condition when this node is at the high level.
The gate of the MOS transistor (T6) 208 is connected to the output end of the inverter (G3) 209 in the mask cell 10, this transistor 208 going into the conducting condition when the output end of the inverter (G3) 209 is at the high level.
When both the bit line 6a and the output end of the inverter (G1) 201 are at the high level, or when both the bit line 6b and the output end of the inverter (G2) 202 are at the high level, the connection node between the MOS transistor (T3) 205 and the MOS transistor (T4) 206 changes to the high level, so that the MOS transistor (T5) 207 conducts.
Therefore, in the case in which the stored data in the data cell 9 differs from the search data 105 on the bit lines 6a and 6b, the MOS transistor (T5) 207 goes into the conducting condition.
When the mask information stored in the mask cell 10 is 1, the MOS transistor (T6) 208 is in the non-conducting condition, and when this mask cell data is 0, this MOS transistor goes into the conducting condition.
The coincidence line 7 is either pulled up to a high potential by a resistance (not shown in the drawing) or is charged to a high potential before the start of the searching operation.
By doing this, as a plurality of associative memory cells 12 are connected to the coincidence line 7 via the respective MOS transistors (T6) 208, if one of the associative memory cells 12 is outputting the low level, the potential on the coincidence line 7 is at the low level, this action representing a wired-AND connection.
When both the MOS transistor (T5) 207 and the MOS transistor (T6) 208 are in the conducting condition, and the coincidence line 7 at the potential of the low level, the associative memory cell 12 outputs the invalid condition "0" to the coincidence line 7, but is in the high level for other states.
That is, the coincidence line 7 is always placed in the high level when the mask information is "1", and when the mask information is "0", if the search data 105 on the bits lines 6a and 6b and the stored data in the data cell 9 coincide, the high level is maintained. However, if the bit line 6a and 6b data and the stored data in the data cell 9 do not coincide, the invalid condition "0", that is, the low level is output.
The shortest mask line 4, as shown in FIG. 8, is pulled up to the high-potential power supply Vdd via the resistance 16, so that it is at the valid condition "1" before the search operation.
The logic circuit 13 is formed by the MOS transistor (T9) 213 and the MOS transistor (T10) 214, which are connected in series between the shortest mask line 4 and the low-potential power supply or ground.
The gate of the MOS transistor (T9) 213 is connected to the coincidence line 7, this transistor going into the conducting condition when the coincidence line 7 is in the valid condition "1", and being in the open-circuit condition when the coincidence line 7 is in the invalid condition "0". The gate of the MOS transistor (T10) 214 is connection to the output end of the inverter (G3) 209 in the mask cell 10, this transistor 214 going into the conducting condition when the output end of the inverter (G3) 209 is at the high level, and being in the open-circuit condition when the output of the inverter 209 is at the low level. That is, when the mask information that is stored in the mask cell 10 is the invalid value of "0", the transistor 214 conducts, and when it is the valid value of "1", the transistor 214 is in the open-circuit condition.
By means of the above, when the coincidence line 7 is the valid value of "1", that is at high level, and also the mask information stored in the mask cell 10 is the invalid value of "0", that is at low level, the logic circuit 13 outputs the invalid value of "0" to the shortest mask line 4, and places this line in the open-circuit condition under other conditions. Accordingly, when the coincidence line 7 is in high level, mask data in the mask cell 10 is output to the shortest mask line 4.
The mask comparator 18 and the mask coincidence line 19 are described below, with reference being made to FIG. 9.
The mask coincidence line 19 is either pulled up through a resistance (not shown in the drawing) or pre-charged to a high potential before the start of a search operation.
The mask comparator 18 is formed by MOS transistor (T11) 215, MOS transistor (T12) 216, and MOS transistor (T13) 217.
The MOS transistor (T11) 215 and the MOS transistor (T12) 216 are connected in series between the bit lines 6a and 6b, the gate of the MOS transistor (T11) 215 being connected to the output end of the inverter (G3) 209 in the mask cell 10. When the output end of the inverter (G3) 209 is at the high level, the MOS transistor (T11) 215 goes into the conducting condition. The gate of the MOS transistor (T12) 216 is connected to the output end of the inverter (G4) 210 in the mask cell 10, and when the output end of the inverter (G4) 210 is at the high level, the MOS transistor (T12) 216 goes into the conducting condition.
The MOS transistor (T13) 217 is connected in series between the low-potential power supply or ground and the mask coincidence line 19, the gate of this transistor 217 being connected to the connection node between the MOS transistor (T11) 215 and the MOS transistor (T12) 216, the MOS transistor (T13) 217 going into the conducting condition when the above-noted connection node is at the high level.
When both the bit line 6a and the output end of the inverter (G3) 209 are at the high level, or when both the bit line 6b and the output end of the inverter (G4) 210 are at the high level, the connection node between the MOS transistor (T11) 215 and the MOS transistor (T12) 216 changes to the high level and the MOS transistor (T13) 217 goes into the conducting condition, but is in the open-circuit condition at other times.
Therefore, in the case in which the mask information stored in the mask cell 10 is different from the search data 105 on the bit lines 6a and 6b, the MOS transistor (T5) 207 goes into the conducting condition, and the mask coincidence line 19 outputs an invalid value "0", that is, the mask coincidence line 19 becomes in the low level. In the case in the which there is coincidence, however, the mask coincidence line 19 is placed in the open-circuit condition (high level).
By doing the above, when a plurality of associative memory cells 12 are connected to the mask coincidence line 19 via respective MOS transistor (T13) 217, if one associative memory cell outputs the low level, the mask coincidence line 19 changes to the low level. In other cases, however, the mask coincidence line 19 is at the high level, this operation representing a wired-AND connection.
From the above-described configuration, the function of the associative memory cell 12 shown in FIG. 8 is implemented.
Returning to FIG. 8, the overall operation of the associative memory 10 is described below.
The n-bit 2-input/1-output selector 17, by means of a control signal 23, selects one from the search data 105-1 to 105-n and the latch output lines 22-1 to 22-n. Each associative memory word 8 outputs valid "1" or invalid "0" to respective mask coincidence line 19. For example, the first associative memory word 8-1 outputs valid "1" or invalid "0" to the mask coincidence line 19-1.
In the above arrangement, all associative memory cells 12 (12-j-1 to 12-j-n) of each associative memory word 8 are wired-AND connected to one mask coincidence line 19(19-j).
When the latch control signal 24 is in the valid state, the n-bit latch 21 stores the states of the shortest mask lines 4-1 to 4-n, the stored states being output to the latch output lines 22-1 to 22-n.
When the latch control signal 24 is valid, the latches 20-1 to 20-n store the states of respective coincidence lines 7-1 to 7-n of the associative memory words 8-1 to 8-n and output these stored states. The outputs of the latches 20-1 to 20-n are wired-logic connected to each mask coincidence line 19 of the words 8-1 to 8-n.
When the search operation is completed, of the mask coincidence lines 19-1 to 19-m indicated coincidence with the search data 105, only the lines that have the fewest bits that were eliminated from the search by the mask information are made valid, with the other lines being invalid.
In this process, valid condition for the mask information is "1", the invalid condition is "0", and the valid and invalid conditions for the shortest mask lines 4-1 to 4-8 are "1" and "0", respectively. The valid and invalid conditions for the coincidence lines 7-1 to 7-5 are "1" and "0", respectively, and the valid and invalid conditions for the mask coincidence lines 19-1 to 19-m are "1" and "0", respectively.
Before the start of the search operation, the mask coincidence lines 19-1 to 19-n are either pulled up to a high-potential power supply Vdd via a resistance (not shown in the drawing) or pre-charged to a high level, so that they are at the valid level of "1".
With respect to the mask coincidence lines 19-j corresponding to the latches 20-j, if the stored data in the latch 20-j is the invalid value of "0", the output of the latch 20-j is "0". Therefore, the corresponding mask coincidence line 19-j goes into invalid condition (low level).
The mask comparator 18 (18-j-k) performs a comparison between the state of the mask information stored in the mask cell 10 (10-j-k)and the shortest mask information on the corresponding bit lines 6 (6-k). If there is coincidence between the two, the corresponding mask coincidence line 19 (19-j) is placed in the high level, and if there is no coincidence, the corresponding mask coincidence line 19 (19-j) is becomes low level (invalid).
In the associative memory word 8 (8-j), therefore, if all MOS transistors (T13) 217 of the mask comparators 18 (18-j) of associative memory cells 12 (12-j-1 to 12-j-n) are in the non-conducting condition and the latches 20 (20-j) outputs high level, the mask coincidence line 19 (19-j) goes into the valid state of "1", but is in the invalid state "0" at other times, this operation representing a wired-AND connection.
That is, only in the case in which there is coincidence between mask information stored in the associative memory word 8 and the values on the bit lines 6-1 to 6-n and also the data stored in the latch 20 (20-j) is at the high level, the mask coincidence line 19 represents by the valid value of "1", it being the invalid value of "0" under other conditions. It is, of course, possible to implement this operation using a conventional logic gate.
FIG. 10 illustrates the operation of the conventional associative memory shown in FIG. 8, and is used to describe the operation of the associative memory 10. The valid states of the mask information is "1" which means mask condition, invalid state of the mask information is "0" which means no mask condition. The valid and invalid states of the shortest mask lines 4-1 to 4-8 are "1" and "0", respectively, and the valid and invalid states of the coincidence line 7-1 to 7-n, and the mask coincidence lines 19-1 to 19-5 is "1" and "0", respectively.
In the associative memory word 8-1, to implement (1, *, *, *), binary data (01, 00, 00, 00) is stored as the stored data, and binary data (00, 10, 11, 11) is stored as mask information.
In the same manner, (2, *, *, *) is stored in the associative memory word 8-2, (1, 2, 2, *) is stored in the associative memory words 8-3, (1, 2, *, *) is stored in the associative memory word 8-4, and (2, 3, 3, *) is stored in the associative memory word 8-5.
The operation of inputting (1, 2, 2, 3) as the search data 105 and performing a search is described below.
First, in accordance with the selection signal 23, the 8-bit, 2-input/1-output selector 17 selects the search data 105, and outputs it to bit lines 6-1 to 6-8.
By doing this, there are coincidence between bit lines and the data (1, *, *, *) in the associative memory word 8-1, and the bit lines and the data (1, 2, 2, *) stored in the associative memory word 8-3 and the data (1, 2, *, *) stored in the associative memory word 8-4.
Therefore, the three coincidence lines 7-1, 7-3 and 7-4 change to the valid "1" state, with the remaining coincidence lines 7-2 and 7-5 being in the invalid "0" state.
At this point, the logic AND value "0" of the mask information "0" corresponding to the shortest mask line 4-1 of the memory word 7-1, the mask information "0" corresponding to the shortest mask line 4-1 of the memory word 7-3 and the mask information "0" corresponding to the shortest mask line 4-1 of the memory word 7-4, is output from the shortest mask line 4-1.
The logic AND value "0" of the mask information "0" corresponding to the shortest mask line 4-2 of the memory word 7-1, the mask information "0" corresponding to the shortest mask line 4-2 of the memory word 7-3 and the mask information "0" corresponding to the shortest mask line 4-2 of the memory word 7-4, is output from the shortest mask line 4-2.
Thereafter, in the same manner, the logical AND value "0" (=1.times.0.times.0) is output from the shortest mask line 4-3, the logical AND value "0" (=1.times.0.times.0) is output from the shortest mask line 4-4, the logical AND value "0" (=1.times.0.times.1) is output from the shortest mask line 4-5, the logical AND value "0" (=1.times.0.times.1) is output from the shortest mask line 4-6, the logical AND value "1" (=1.times.1.times.1) is output from the shortest mask line 4-7, and the logical AND value "1" (=1.times.1.times.1) is output from the shortest mask line 4-8.
Therefore, the shortest mask lines 4-1 to 4-8 output the binary value of 00000011, respectively, and the n-bit latch 21 internally stores the states of the shortest mask lines 4-1 to 4-8. The binary value 00000011 is stored in the n-bit latch 21, this n-bit latch 21 outputting the value 00000011 to the latch output line 22 (22-1 to 22-n).
In this condition, the latch control signal 24 becomes valid, and the latches 20-1 to 20-5 store the states of the corresponding coincidence lines 7-1 to 7-5, simultaneously, "0" is stored in latch 20-1, "0" is stored in latch 20-2, "1" is stored in latch 20-3, "1" is stored in latch 20-4, and "0" is stored in latch 20-5.
Next, in accordance with the selection signal 23, the 8-bit 2-input/1-output selector 17 selects the latch output line 22, the information 00000011 thereof being output to the corresponding bit lines 6-1 to 6-8, after which the associative memory 10 starts the second search operation.
At the second search operation, the states of the mask coincidence lines 19-1 to 19-8 are used, and the states of the coincidence lines 7-1 to 7-8 are ignored.
Before the start of the second search operation, the mask coincidence lines 19-1 to 19-8 are either pre-charged to a high level or pulled up to a high level via a resistance (not shown in the drawing), so that they are in the valid state "1".
With respect to the 00000011 states of the bit lines 6-1 to 6-8, the states of the bit lines 6-1 to 6-8 completely coincide with the mask information stored in the associative memory words 8-3 and 8-5, so that the corresponding coincidence lines 19-3 and 19-5 are placed in the open-circuit condition.
Because the mask information stored in the other associative memory words 8-1, 8-2, and 8-4 does not coincide, the invalid state "0" is output at the corresponding mask coincidence lines 19-1, 19-2, and 19-4.
The latch 20-1 outputs the stored state "1" to the corresponding coincidence line 19-1, the latch 20-2 outputs the stored state "0" to the corresponding coincidence line 19-2, the latch 20-3 outputs the state "1" to the corresponding coincidence line 19-3, the latch 20-4 outputs the state "1" to the corresponding coincidence line 19-4, and the latch 20-5 outputs the state "0" to the corresponding coincidence line 19-5.
Therefore, for the mask coincidence line 19-1 of the associative memory word 8-1, because the mask comparator output "0" and the latch 20-1 output "1", the state of the mask coincidence line 19-1 is the invalid "0" state.
For the mask coincidence line 19-2 of the associative memory word 8-2, because the mask comparator output "0" and the latch 20-2 output "0", the state of the mask coincidence line 19-2 is the invalid "0" state.
For the mask coincidence line 19-3 of the associative memory word 8-3, because the mask comparator output "1" and the latch 20-3 output "1", the state of the mask coincidence line 19-3 is the invalid "1" state.
For the mask coincidence line 19-4 of the associative memory word 8-4, because the mask comparator output "0" and the latch 20-4 output "1", the state of the mask coincidence line 19-4 is the invalid "0" state.
For the mask coincidence line 19-5 of the associative memory word 8-5, because the mask comparator output "0" and the latch 20-5 output "0", the state of the mask coincidence line 19-5 is the invalid "0" state.
In accordance with the above, it can be seen that only the mask coincidence line which correspond to the associative memory words 8-1 to 8-5 that coincide with the search data 105, at the first search operation, taking into consideration the mask information, and that coincide with the states of the shortest mask lines 4-1 to 4-8 that is obtained at the end of the second search operation.
The associative memory word that corresponds to the mask coincidence lines that is in the valid state at the end of the second search operation is the words for which the mask information has the fewest valid bits, and the word for which there is coincidence with the search data 105, over the longest parts.
FIG. 11 is a timing diagram showing the above-noted first and second search operations, in which [1] to [4] indicate clock cycles.
In clock cycle [1], all the bit lines 6, the coincidence lines 7, and the mask coincidence lines 19 are pre-charged to a high level "1".
In the clock cycle [2], at the rising edge of the clock, bit information corresponding to search data is output to each bit line. If this bit information and the corresponding stored data bit information in each associative memory word coincide or if the bit data of the mask information corresponding to that of search data 105 is "1", the coincidence line of that memory word becomes the valid value "1", with the coincidence lines of other associative memory words being the invalid value of "0". Additionally, the logical AND of the mask bit information corresponding to associative memory words in the valid state is output to the shortest mask lines. At this point the latch control signal 24 is made active, so that the state of the coincidence line of each memory word is stored in latch 20. The bit information of each shortest mask line is stored in the n-bit latch 21, and is also output to the latch output line 22.
Next, in the clock cycle [3], all bit lines, coincidence lines 7 and mask coincidence lines 19 are pre-charged to a high level. With regard to the mask coincidence lines 19, pre-charging to a high level is only done to the mask coincidence lines of associative memory words for which a "1" is stored in the latch 20.
In the clock cycle [4], at the rising edge of the clock, in accordance with the selection signal 23, the bit information at each latch output line 22 is output to the corresponding bit line 6. Then only the mask coincidence lines 19 for which the bit information on the latch output lines 22 coincides with the mask information stored in the associative memory word and for which "1" is stored in the latch 20 are output as the valid value of "1".
As described above, using an associative memory with a shortest mask output function of the prior art, of the word for which there is coincidence, considering the mask information, at two clocks, the mask coincidence line of the associative memory word that has the shortest bit length of valid mask bits, that is, the mask coincidence line of word that has the longest parts in coincidence with the search data is set to the valid value of "1", enabling selection of this word.
In the above-described associative memory with a shortest mask output function according to prior art, however, in the above-noted first and second search operations, because the search data is performed by using bit lines 6-1 to 6-n, when a continuous search is performed, it is not possible to perform pipeline searching. That is, the next search cannot be started until the second search of the previous search operation has been completed.
For this reason, there is the problem with regard to searching performance that only an excessively small number of searches can performed within a given period of time.
Accordingly, it is an object of the present invention, in consideration of the above-noted drawback of the prior art, to provide an associative memory which enables the start of the first search operation of a subsequent search to be started simultaneously with the execution of the second search operation of the previous search, thereby providing an improvement in the number of searches that can be performed in a given period of time.